package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Code47 {
	/*
	 * 2B了
	 * 下面求的是所有的子集
	 */
    public List<List<Integer>> permuteUniqueII(int[] nums) {
    	List<List<Integer>> ans=new ArrayList<List<Integer>>();
    	int n=nums.length;
    	if(n==0)
    		return ans;
    	int size=1<<n;
    	int i,j;
    	Set<StringBuilder> vis=new HashSet<StringBuilder>();
    	
    	for(i=0;i<size;i++){
    		List<Integer> list=new ArrayList<Integer>();
    		StringBuilder sb=new StringBuilder();
    		for(j=0;j<n;j++){
    			if((i&(1<<j))>0){
    				list.add(nums[j]);
    				sb.append(",");
    				sb.append(nums[j]);
    			}
    			if(vis.contains(sb)){
    				continue;
    			}
    			vis.add(sb);
    			ans.add(list);
    		}
    	}
    	return ans;
    }
    
    /*
     * 求的是所有的全排列
     * dfs
     */
    
    public void dfs(int n,int step,int[] rec,int[] nums,boolean[] record,List<List<Integer>> result){
    	int i;
    	if(n==step){
    		List<Integer> list=new ArrayList<Integer>();
    		for(i=0;i<n;i++){
				list.add(rec[i]);
    		}
			result.add(list);
			return ;
    	}
    	for(i=0;i<n;i++){
    		if(record[i] || 
    				(i-1>=0 && nums[i]==nums[i-1] && !record[i-1]))
    			/*
    			 * nums[i]==nums[i-1],避免计算重复的
    			 * 很巧妙的方法
    			 * 不需要用其他笨拙的方法再对结果去重
    			 */
    			continue;
    		if(!record[i]){
    			record[i]=true;
    			rec[step]=nums[i];
    			dfs(n,step+1,rec,nums,record,result);
    			record[i]=false;
    		}
    	}
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
    	List<List<Integer>> ans=new ArrayList<List<Integer>>();
    	int n=nums.length;
    	if(n==0) return ans;
    	Arrays.sort(nums);
    	int[] rec=new int[n];
    	boolean[] record=new boolean[n];
    	Set<String> vis=new HashSet<String>();
    	dfs(n,0,rec,nums,record,ans);
    	return ans;
    }
    
    public static void main(String[] args){
    	int[] nums={3,3,0,0,2,3,2};
    	new Code47().permuteUnique(nums);
//    	Set<String> vis=new HashSet<String>();
//    	String s1="ab";
//    	String s2="ab";
//    	vis.add(s1);
//    	boolean flag=vis.contains(s2);
//    	flag=true;
    }
}
